package application.models.models;

import java.io.IOException;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;

import application.controllers.PeriodController;
import application.models.collections.CarCollection;
import application.models.collections.ReservationCollection;
import application.models.datalayer.Date;
import application.models.exceptions.CarMatchException;
import application.models.exceptions.InvalidAttributeException;

/**
 * Finds cars for reservations dynamically
 * Bug: Cannot handle Car- and ReservationModels that has been edited but not saved!
 * 
 * NB: We did not have the time for anything but a naive implementation
 * The algorithm used by the class only needs all reservations between two safe spots
 * A safe spot is a day without any reservation or any date before the current date
 * If all reservations with a safe spot is used in the mapping, double booking is prevented
 * We did not have the time to implement an algorithm finding these safe spots
 * 
 * @author Philip Rasmussen & Morten Therkildsen
 */
public class ReservationToCarMatcher {

	// Any reservation it touches that has no number_plate criteria gets one based on the mapped car, IF the start date < current date
	
	/**
	 * Attempts to map all given reservations with a matching car without double booking the cars
	 * 
	 * @param reservations			The reservations to find cars for
	 * @return						A map with each reservation mapped to a car
	 * @throws CarMatchException	If not all reservation could be mapped to a car
	 */
	public static Map<ReservationModel, CarModel> matchCarsToReservations(Set<ReservationModel> reservations) throws CarMatchException {
		
		
		Set<ReservationModel> allReservations = new HashSet<ReservationModel>(reservations);
		ReservationCollection collection = new ReservationCollection();
		
		try {
			
			// Load all reservations and add them to the reservations, that will be mapped
			collection.load();
			for(ReservationModel model : collection){

				allReservations.add(model);
			}

			// Map each reservation to a model
			Map<ReservationModel, CarModel> map = mapReservationsToCars(allReservations);
			if(map == null) throw new CarMatchException("Not all reservations could be mapped to a car");
			
			Date now = PeriodController.getCurrentDay();
			
			// For the future: Any reservation that has a start date before this day cannot be changed
			// Make sure the car is not changed by settting the registration_number criteria to the registration number of the matched car
			for(ReservationModel reservation : map.keySet()){

				try{
					
					if(((Date) reservation.getAttribute("starts")).getTime() < now.getTime()){
						
						if(reservation.getAttribute("registration_number") == null){
							
							reservation.setAttribute(
														"registration_number",
														map.get(reservation).getAttribute("registration_number")
													);
						}
					}
					
				} catch(InvalidAttributeException e){
					
					throw new RuntimeException("Unexpeced logic failure", e);
				}
			}
			
			// Only return the mappings for the set that was asked for
			Map<ReservationModel, CarModel> result = new HashMap<ReservationModel, CarModel>();

			for(ReservationModel addToResult : reservations){

				result.put(addToResult, map.get(addToResult));
			}

			return result;
		} catch(IOException e){ throw new RuntimeException("Datalayer fail", e);}
	}

	/**
	 * Attempts to map all given reservations with a matching car without double booking the cars
	 * In order to prevent over booking the passed reservations MUST NOT overlap with any reservation not passed along.
	 * 
	 * @param reservations	The reservations to find cars for
	 * @return a map with reservations and their found cars or null if not all reservations could be assigned a car
	 */
	private static Map<ReservationModel, CarModel> mapReservationsToCars(Set<ReservationModel> reservations){

		// STEP 1: Populate the carMap and reservationMap with models that matches. Also populate reservationCompetitorMap with overlapping reservations

		// Maps each reservation to the car they match
		Map<ReservationModel, Set<CarModel>> reservationMap = new HashMap<ReservationModel, Set<CarModel>>();
		
		// Maps each car to the reservations which match them
		Map<ReservationModel, Set<ReservationModel>> reservationCompetitorMap = new HashMap<ReservationModel, Set<ReservationModel>>();
		
		// Maps each reservation to overlapping reservations
		Map<CarModel, Set<ReservationModel>> carMap = new HashMap<CarModel, Set<ReservationModel>>();
		
		for(ReservationModel reservation : reservations){
			
			CarCollection matchingCars = reservation.getMatchingCars();
			
			Set<CarModel> modelSet = new HashSet<CarModel>();
			reservationMap.put(reservation, modelSet); // Add car matches for the reservation
			
			// Add reservation matches for the car
			for(CarModel model : matchingCars){
				
				modelSet.add(model);
				
				if(!carMap.containsKey(model)) carMap.put(model, new HashSet<ReservationModel>());
				carMap.get(model).add(reservation);
			}
			
			// Add reservation for each overlapping reservation and vice versa
			reservationCompetitorMap.put(reservation, new HashSet<ReservationModel>());
			try{

				long starts = ((Date) reservation.getAttribute("starts")).getTime();
				long ends = ((Date) reservation.getAttribute("ends")).getTime();
			
				for(ReservationModel model : reservationCompetitorMap.keySet()){
				
					long starts2 = ((Date) model.getAttribute("starts")).getTime();
					long ends2 = ((Date) model.getAttribute("ends")).getTime();
					
					if(
							starts >= starts2 && starts < ends2 ||	// start included in potential competitor
							ends <= ends2 && ends > starts2			// end included in potential competitor
					){
						// They are competitors if we get to here!
						reservationCompetitorMap.get(reservation).add(model);
						reservationCompetitorMap.get(model).add(reservation);
					}
				}
				
				// At this point we have added the reservation itself as a competitor - undo!
				reservationCompetitorMap.get(reservation).remove(reservation);
				
			} catch(InvalidAttributeException e){
				
				return null; // Error
			}
		}
		
		// STEP 2: Attempt to map a car to each reservation
		
		Map<ReservationModel, CarModel> results = new HashMap<ReservationModel, CarModel>();
		ReservationModel[] sortedKeys = reservationMap.keySet().toArray(new ReservationModel[0]);
		
		// While we got any unmapped reservations left
		while(reservationMap.keySet().size() > 0){
			
			sortedKeys = mapReservationsToCarsSorter(sortedKeys, reservationMap);

			ReservationModel reservationModel = sortedKeys[0];
			
			// Find the car matched by the fewest overlapping reservations
			
			Iterator<CarModel> it = reservationMap.get(reservationModel).iterator();
			
			if(!it.hasNext()) return null;
			
			CarModel carResult = it.next();
			Set<ReservationModel> sharedCarMatches = new HashSet<ReservationModel>(carMap.get(carResult));
			sharedCarMatches.retainAll(reservationCompetitorMap.get(reservationModel));
			int usedByReservationCompetitorsCount = sharedCarMatches.size();
			
			while(it.hasNext()){
				
				CarModel competitor = it.next();
				Set<ReservationModel> reservationCompetitorsSharedCarMatches = new HashSet<ReservationModel>(carMap.get(competitor));
				reservationCompetitorsSharedCarMatches.retainAll(reservationCompetitorMap.get(reservationModel));
				int competitorUsedByReservationCompetitorsCount = reservationCompetitorsSharedCarMatches.size();
				
				// if fewer reservations match the competitor it becomes the new result
				if(usedByReservationCompetitorsCount > competitorUsedByReservationCompetitorsCount){
					
					carResult = competitor;
					usedByReservationCompetitorsCount = competitorUsedByReservationCompetitorsCount;
				}
			}
		
			results.put(reservationModel, carResult);
			
			// Cleanup - unneeded cleanups may be commented out
			
			for(ReservationModel reservation : reservationCompetitorMap.get(reservationModel)){
				
				// Remove resultCar match references from competitors
				reservationMap.get(reservation).remove(carResult);
				
				// Remove competitor match references from resultCar
				carMap.get(carResult).remove(reservation);
				
				// Remove reservationModel references from competitors
				reservationCompetitorMap.get(reservation).remove(reservationModel);
			}
			// Remove the reservationModel from reservationCompetitorMap
			reservationCompetitorMap.remove(reservationModel);
			
			// Remove the reservation as a match for all matching cars
			for(CarModel car : reservationMap.get(reservationModel)){
				
				carMap.get(car).remove(reservationModel);
			}
			// Remove the reservation from the reservationMap
			reservationMap.remove(reservationModel);
			
			sortedKeys[0] = null; // The reservation has been processed
		}

		return results;
	}
	
	/**
	 * Sorts an array of reservation models based on their matching cars count in the reservation map passed along
	 * 
	 * @param sortedKeys	the array to sort
	 * @param reservationMap	the map mapping each reservation to a set of matching car models
	 * @return an array of ascending sorted reservation models based on their matching cars count
	 */
	private static ReservationModel[] mapReservationsToCarsSorter(ReservationModel[] sortedKeys, Map<ReservationModel, Set<CarModel>> reservationMap){
		
		mapReservationsToCarsSorterHelper(sortedKeys, reservationMap, 0, sortedKeys.length-1);
		
		return sortedKeys;
	}
	
	/**
	 * Sort helper used by mapReservationsToCarsSorter using quicksort.
	 * Elements in keys are sorted ascending based on their number of cars in the values map, where null is greater than anything else.
	 * 
	 * @param keys			The array to sort
	 * @param values		The map containing the values to compare
	 * @param fromKeyIndex	The index in the array to sort from
	 * @param toKeyIndex	The index in the array to sort to
	 */
	private static void mapReservationsToCarsSorterHelper(ReservationModel[] keys, Map<ReservationModel, Set<CarModel>> values, int fromKeyIndex, int toKeyIndex){
		
		// Sorts the elements of keys ascending based on their number of matched cars using quicksort.
		// 0 is considered greater than any other value.
		// Quicksort is faster than heapsort on average:
		// Quicksort will not repeatedly perform worse, because we maintain a data structure after first call
				
		if (fromKeyIndex >= toKeyIndex) return;
		
		int lowIndex = fromKeyIndex;
		int highIndex = toKeyIndex;
		
		int middleIndex = (lowIndex + highIndex) / 2;
		Set<CarModel> set = values.get(keys[middleIndex]);
		int pivotValue = set == null ? 1 : set.size()-Integer.MAX_VALUE;
		
		// Sorts all values higher than the pivotValue after the index of the pivot
		// Sorts all values lower than the pivotValue before the index of the pivot
		while(lowIndex < highIndex){
			
			// Find the index of the first value greater than the pivotValue from the start
			while(
					lowIndex < middleIndex &&
					(values.get(keys[lowIndex]) == null ? 1 : values.get(keys[lowIndex]).size()-Integer.MAX_VALUE) <= pivotValue
			) ++lowIndex;
			
			// Find the index of the first value less than the pivotValue from the end
			while(
					middleIndex < highIndex &&
					(values.get(keys[highIndex]) == null ? 1 : values.get(keys[highIndex]).size()-Integer.MAX_VALUE) >= pivotValue
			) --highIndex;
			
			// Swap the two values being at the wrong side of the pivot
			if(lowIndex < highIndex){
				
				ReservationModel temp = keys[highIndex];
				keys[highIndex] = keys[lowIndex];
				keys[lowIndex] = temp;
			}
			
		}
		
		// Sort the upper and lower parts separately
		mapReservationsToCarsSorterHelper(keys, values, fromKeyIndex, lowIndex);
		mapReservationsToCarsSorterHelper(keys, values, lowIndex == fromKeyIndex ? lowIndex+1 : lowIndex, toKeyIndex);
	}
}
